#include <iostream>
using namespace std;

/*
 * 问题来源：在某些场合会遇到针对大数的取模，这个大数一般以整数幂来表示
 * 并且可能超计算机整形的表示范围
 * 所以需要一些特别的方法来计算大数取模问题
 */

/*
 * 问题： 求a^b % m 
 * 解决方法：Montgomery算法
 * 描述：a^b表达式中b的二进制表示为b1b2b3...bn, 即 bn*2^0 + ...b1*2^
 *       a^b 可以表示为a^(bn*2^0 + ... + b1*2^n)
 *       又根据同余性质:对任意整数b 有 (ab)%m = (b * (a % m)) % m
 *       任意相除两项 a^2^(i+1) = (a^2^i)^2
 */

int mod(int a,int b,int m){
    int result = 1;
    int base = a;
    while(b > 0){
        if(b & 1){
            result = (result * base) % m;
        }
        base = (base * base) % m;
        b >>= 1;
    }
    return result;
}

int
main() {
    cout << "9^10 % 1007 = " << mod(9, 10, 1007) << endl; 
    return 0;
}
